{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #小张刷题计划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #小张刷题计划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>为了提高自己的代码能力，小张制定了 <code>LeetCode</code> 刷题计划，他选中了 <code>LeetCode</code> 题库中的 <code>n</code> 道题，编号从 <code>0</code> 到 <code>n-1</code>，并计划在 <code>m</code> 天内<strong>按照题目编号顺序</strong>刷完所有的题目（注意，小张不能用多天完成同一题）。</p>\n",
    "\n",
    "<p>在小张刷题计划中，小张需要用 <code>time[i]</code> 的时间完成编号 <code>i</code> 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止&ldquo;小张刷题计划&rdquo;变成&ldquo;小杨刷题计划&rdquo;，小张每天最多使用一次求助。</p>\n",
    "\n",
    "<p>我们定义 <code>m</code> 天中做题时间最多的一天耗时为 <code>T</code>（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 <code>T</code>是多少。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>time = [1,2,3,3], m = 2</code></p>\n",
    "\n",
    "<p>输出：<code>3</code></p>\n",
    "\n",
    "<p>解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>time = [999,999,999], m = 4</code></p>\n",
    "\n",
    "<p>输出：<code>0</code></p>\n",
    "\n",
    "<p>解释：在前三天中，小张每天求助小杨一次，这样他可以在三天内完成所有的题目并不花任何时间。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= time.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= time[i] &lt;= 10000</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xiao-zhang-shua-ti-ji-hua](https://leetcode.cn/problems/xiao-zhang-shua-ti-ji-hua/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xiao-zhang-shua-ti-ji-hua](https://leetcode.cn/problems/xiao-zhang-shua-ti-ji-hua/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,3]\\n2', '[1,2,3,3,3]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        n=len(time)\n",
    "        if n<=m:\n",
    "            return 0\n",
    "        def check(k):\n",
    "            q=[]\n",
    "            now=0\n",
    "            p=False\n",
    "            c=1\n",
    "            for t in time:\n",
    "                #print(c,now,q,p,t)\n",
    "                q.append(t)\n",
    "                now+=t\n",
    "                if now>k:\n",
    "                    if p:\n",
    "                        p=False\n",
    "                        q=[t]\n",
    "                        now=t\n",
    "                        if now>k:\n",
    "                            p=True\n",
    "                            q=[]\n",
    "                            now=0\n",
    "                        c+=1\n",
    "                    else:\n",
    "                        p=True\n",
    "                        q.sort()\n",
    "                        now-=q[-1]\n",
    "            if now>k and p:\n",
    "                c+=1\n",
    "            #print(k,c)\n",
    "            return c<=m \n",
    "        ans=bisect_left(range(sum(time)),True,key=check)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = 1000000001\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            tmp_max = 0\n",
    "            n = 1\n",
    "            total = 0\n",
    "            for t in time:\n",
    "                tmp_max = t if tmp_max < t else tmp_max\n",
    "                total += t\n",
    "                if total - tmp_max > mid:\n",
    "                    n += 1\n",
    "                    total = t\n",
    "                    tmp_max = t\n",
    "            if n > m:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(T, m):\n",
    "            cost, most = 0, 0\n",
    "            for t in time:\n",
    "                most = max(most, t)\n",
    "                if cost + t - most <= T:\n",
    "                    cost += t\n",
    "                else:\n",
    "                    m -= 1\n",
    "                    if m == 0:\n",
    "                        return False\n",
    "                    cost, most = t, t\n",
    "            return True\n",
    "\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid, m):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        left = 0\n",
    "        right = sum(time)\n",
    "        while(left < right):\n",
    "            mid = (left + right) >> 1\n",
    "            # 若符合\n",
    "            if self.check(time, m, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def check(self, time: List[int], m: int, limit) -> bool:\n",
    "        temp_sum = 0\n",
    "        temp_max = time[0]\n",
    "        days = 1\n",
    "        for t in time[1:]:\n",
    "            if temp_sum + min(temp_max, t) <= limit:\n",
    "                temp_sum += min(temp_max, t)\n",
    "                temp_max = max(temp_max, t)\n",
    "            else:\n",
    "                temp_sum = 0\n",
    "                temp_max = t\n",
    "                days += 1\n",
    "\n",
    "        return days <= m\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = sum(time)\n",
    "        while l < r:\n",
    "            middle = (l + r) >> 1\n",
    "            if self.check(middle, time, m):\n",
    "                r = middle\n",
    "            else:\n",
    "                l = middle + 1\n",
    "        return l\n",
    "\n",
    "    def check(self, check_time: int, time: List[int], m: int) -> bool:\n",
    "        max_cost_time = time[0]\n",
    "        cost_days = 1\n",
    "        use_time = 0\n",
    "        for i in time[1:]:\n",
    "            if use_time + min(max_cost_time, i) <= check_time:\n",
    "                use_time += min(max_cost_time, i)\n",
    "                max_cost_time = max(max_cost_time, i)\n",
    "            else:\n",
    "                cost_days += 1\n",
    "                max_cost_time = i\n",
    "                use_time = 0\n",
    "        return cost_days <= m\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "# 二分问题\n",
    "        if m>= len(time):\n",
    "            return 0\n",
    "        start = 0\n",
    "        end = sum(time)//m + 1\n",
    "        while start < end:\n",
    "            mid = (start + end)//2\n",
    "            curD = 1\n",
    "            curT = 0\n",
    "            maxT = 0\n",
    "            for t in time:\n",
    "                curT += t\n",
    "                maxT = max(maxT,t)\n",
    "                if curT-maxT > mid:\n",
    "                    curT = t \n",
    "                    curD += 1\n",
    "                    maxT = t\n",
    "            if curD > m:\n",
    "                start = mid + 1\n",
    "            else:\n",
    "                end = mid\n",
    "        return end\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, duration: List[int], m: int) -> int:\n",
    "        L = len(duration)\n",
    "        if m >= L:\n",
    "            return 0\n",
    "        a = sorted(duration)\n",
    "        T = sum(a[0:L-m])//m - 1\n",
    "        l, r = T, 1000000000\n",
    "        flag = 0\n",
    "        T_min = 1000000000\n",
    "        while l < r:\n",
    "            T = (l+r)//2\n",
    "            i = 0\n",
    "            count = m\n",
    "            flag = 0\n",
    "            while count > 0:\n",
    "                d_tmp_max = 0\n",
    "                d_tmp_sum = 0\n",
    "                i -= 1\n",
    "                while not d_tmp_sum - d_tmp_max > T:\n",
    "                    i += 1\n",
    "                    if i >= L:\n",
    "                        l, r = l, T\n",
    "                        flag = 1\n",
    "                        count = 0\n",
    "                        T_min = min(T, T_min)\n",
    "                        break\n",
    "                    d_tmp_max = max(d_tmp_max, duration[i])\n",
    "                    d_tmp_sum += duration[i]\n",
    "                count -= 1\n",
    "            if flag != 1:\n",
    "                l, r = T+1, r\n",
    "        return T_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        \n",
    "        def check(T, m):\n",
    "            cost, most, day = 0, 0, 1\n",
    "            for t in time:\n",
    "                most = max(most, t)\n",
    "                if cost + t - most <= T:   # 可以将t与前面算进同一天\n",
    "                    cost += t\n",
    "                else:\n",
    "                    day += 1   # 新起一天\n",
    "                    if day > m:\n",
    "                        return False\n",
    "                    cost, most = t, t\n",
    "            return True\n",
    "\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid, m):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return right\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, duration: List[int], m: int) -> int:\n",
    "        L = len(duration)\n",
    "        if m >= L:\n",
    "            return 0\n",
    "        a = sorted(duration)\n",
    "        T = sum(a[0:L-m])//m - 1\n",
    "        l, r = T, 1000000000\n",
    "        flag = 0\n",
    "        T_min = 1000000000\n",
    "        while l < r:\n",
    "            T = (l+r)//2\n",
    "            i = 0\n",
    "            count = m\n",
    "            flag = 0\n",
    "            while count > 0:\n",
    "                d_tmp_max = 0\n",
    "                d_tmp_sum = 0\n",
    "                i -= 1\n",
    "                while not d_tmp_sum - d_tmp_max > T:\n",
    "                    i += 1\n",
    "                    if i >= L:\n",
    "                        l, r = l, T\n",
    "                        flag = 1\n",
    "                        count = 0\n",
    "                        T_min = min(T, T_min)\n",
    "                        break\n",
    "                    d_tmp_max = max(d_tmp_max, duration[i])\n",
    "                    d_tmp_sum += duration[i]\n",
    "                count -= 1\n",
    "            if flag != 1:\n",
    "                l, r = T+1, r\n",
    "        return T_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        L, R = 0, sum(time)\n",
    "        while L < R:            #二分查找框架！！！！  找符合条件的最左端的 \n",
    "            mid = (L + R) >> 1\n",
    "            if self.check(mid, time, m) == True:\n",
    "                R = mid\n",
    "            else:\n",
    "                L = mid + 1\n",
    "        return L \n",
    "\n",
    "    def check(self, limit: int, time: List[int], m: int) -> bool:\n",
    "        use_day = 1\n",
    "        cur_sum = 0         #能求助就求助  省力气\n",
    "        cur_max = time[0]\n",
    "        for t in time[1: ]:\n",
    "            if cur_sum + min(cur_max, t) <= limit:  #添加也要加那个小的  万一新加的比cur_max大\n",
    "                cur_sum += min(cur_max, t)          #维持cur_sum\n",
    "                cur_max = max(cur_max, t)           #维持cur_max\n",
    "            else:\n",
    "                use_day += 1                        #超了，就只能明天再搞\n",
    "                cur_sum = 0                         #清0\n",
    "                cur_max = t                         #t要明天再搞 t是明天第一个\n",
    "        return use_day <= m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(mid):\n",
    "            cnt = 1\n",
    "            sum = 0\n",
    "            maxT = 0\n",
    "            for t in time:\n",
    "                sum += t\n",
    "                maxT = max(maxT, t)\n",
    "                if sum - maxT > mid:\n",
    "                    sum = t\n",
    "                    maxT = t\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) > m:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        #在有序的用时最多一天表中二分搜寻第一个满足使用次数为m的\n",
    "        #split量也是找\"至少使用的次数\"，这样可以保证如果低于min的T，那至少也得多使用，因此不满足\n",
    "        min_time=0\n",
    "        max_time=sum(time)\n",
    "        def choices(time,max_time):\n",
    "            choice=1\n",
    "            cur_time=0\n",
    "            cur_max=0\n",
    "            for t in time:\n",
    "                cur_time+=t\n",
    "                cur_max=max(cur_max,t)\n",
    "                if cur_time-cur_max>max_time:\n",
    "                    #加上这一天t后怎么都会超，因此不能加，考虑放到下一天\n",
    "                    choice+=1\n",
    "                    #放到第一天，并且把它消掉,似乎无所谓\n",
    "                    cur_time=t\n",
    "                    cur_max=t\n",
    "            return choice\n",
    "        def lower_bound(time):\n",
    "            left=min_time\n",
    "            right=max_time\n",
    "            while left<=right:\n",
    "                mid=left+(right-left)//2\n",
    "                choice=choices(time,mid)\n",
    "                if choice>m:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            return left\n",
    "        return lower_bound(time)\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        lo, hi = 0, sum(time)\n",
    "\n",
    "        while lo < hi:\n",
    "\n",
    "            mid = (lo+hi) // 2\n",
    "\n",
    "            if self.check(time, mid, m):\n",
    "\n",
    "                hi = mid\n",
    "\n",
    "            else:\n",
    "\n",
    "                lo = mid + 1\n",
    "\n",
    "        return lo\n",
    "\n",
    "\n",
    "\n",
    "    def check (self,time,mid,m):\n",
    "        cnt = 0 # 大于每日时间的天数\n",
    "        max_ = 0 #最大的单个时间\n",
    "        s = 0 #时间的累加\n",
    "        for t in time:\n",
    "            max_ = max(max_,t)\n",
    "            s+=t\n",
    "            if s - max_ > mid:\n",
    "                cnt += 1\n",
    "                s = t\n",
    "                max_ = t\n",
    "        return cnt<m #小于m则说明可以选mid作为答案，大不了每天都问"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        L, R = 0, sum(time)\n",
    "        while L < R:\n",
    "            mid = (L + R) >> 1\n",
    "            if self.check(mid, time, m) == True:\n",
    "                R = mid\n",
    "            else:\n",
    "                L = mid + 1\n",
    "        return L \n",
    "\n",
    "    def check(self, limit: int, time: List[int], m: int) -> bool:\n",
    "        use_day = 1\n",
    "        cur_sum = 0\n",
    "        cur_max = time[0]\n",
    "        for t in time[1: ]:\n",
    "            if cur_sum + min(cur_max, t) <= limit:\n",
    "                cur_sum += min(cur_max, t)\n",
    "                cur_max = max(cur_max, t)\n",
    "            else:\n",
    "                use_day += 1\n",
    "                cur_sum = 0\n",
    "                cur_max = t\n",
    "        return use_day <= m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def cost(x):\n",
    "            _ = 0\n",
    "            _max = time[0]\n",
    "            t = 0\n",
    "            for i in time:\n",
    "                _max = max(_max, i)\n",
    "                _ += i\n",
    "                if _ - _max <= x:\n",
    "                    continue\n",
    "                else:\n",
    "                    _ = i\n",
    "                    _max = i\n",
    "                    t += 1\n",
    "            return t+1\n",
    "        \n",
    "        left, right = 0, sum(time)-max(time)\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if cost(mid) <= m:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        \n",
    "        return left \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        lo, hi = 0, sum(time)\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            if self.check(time, mid, m):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo\n",
    "\n",
    "    def check(self, time, mid, m):\n",
    "        cnt = 0\n",
    "        max_ = 0\n",
    "        s = 0\n",
    "        for t in time:\n",
    "            max_ = max(max_, t)\n",
    "            s += t\n",
    "            if s - max_ > mid:\n",
    "                cnt += 1\n",
    "                s = t\n",
    "                max_ = t\n",
    "        return cnt < m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        lo, hi = 0, sum(time)\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            if self.check(time, mid, m):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo\n",
    "\n",
    "    def check(self, time, mid, m):\n",
    "        cnt = 0\n",
    "        max_ = 0\n",
    "        s = 0\n",
    "        for t in time:\n",
    "            max_ = max(max_, t)\n",
    "            s += t\n",
    "            if s - max_ > mid:\n",
    "                cnt += 1\n",
    "                s = t\n",
    "                max_ = t\n",
    "        return cnt < m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        L, R = 0, sum(time)\n",
    "        while L < R:            #二分查找框架！！！！  找符合条件的最左端的 \n",
    "            mid = (L + R) >> 1\n",
    "            if self.check(mid, time, m) == True:\n",
    "                R = mid\n",
    "            else:\n",
    "                L = mid + 1\n",
    "        return L \n",
    "\n",
    "    def check(self, limit: int, time: List[int], m: int) -> bool:\n",
    "        use_day = 1\n",
    "        cur_sum = 0         #能求助就求助  省力气\n",
    "        cur_max = time[0]\n",
    "        for t in time[1: ]:\n",
    "            if cur_sum + min(cur_max, t) <= limit:  #添加也要加那个小的  万一新加的比cur_max大\n",
    "                cur_sum += min(cur_max, t)          #维持cur_sum\n",
    "                cur_max = max(cur_max, t)           #维持cur_max\n",
    "            else:\n",
    "                use_day += 1                        #超了，就只能明天再搞\n",
    "                cur_sum = 0                         #清0\n",
    "                cur_max = t                         #t要明天再搞 t是明天第一个\n",
    "        return use_day <= m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(mid):\n",
    "            cnt,s,_max=0,0,0\n",
    "            for n in time:\n",
    "                s+=n\n",
    "                _max=max(_max,n)\n",
    "                if s>mid+_max:\n",
    "                    cnt+=1\n",
    "                    s=n\n",
    "                    _max=n\n",
    "            return cnt+(s>0)\n",
    "\n",
    "        l,r=0,sum(time)\n",
    "        while l<r:\n",
    "            mid=(l+r)>>1\n",
    "            if check(mid)>m: l=mid+1\n",
    "            else: r=mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def codeDay(self, time:List[int], max_time:int) -> int:\n",
    "        i = -1\n",
    "        d = 0\n",
    "        sum_time = 0\n",
    "        flag = 0\n",
    "        maxVal = 0\n",
    "        while i < len(time) - 1:\n",
    "            i += 1\n",
    "            maxVal = max(maxVal, time[i])\n",
    "            sum_time += time[i]\n",
    "            if sum_time > max_time:\n",
    "                if flag == 0:\n",
    "                    sum_time -= maxVal\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    d += 1\n",
    "                    sum_time = 0\n",
    "                    maxVal = 0\n",
    "                    i -= 1\n",
    "                    flag = 0\n",
    "        return d + 1\n",
    "    \n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        if m >= len(time):\n",
    "            return 0\n",
    "        else:\n",
    "            left, right = min(time), sum(time)\n",
    "            while left < right:\n",
    "                mid = int(left + (right - left)/2)\n",
    "                d = self.codeDay(time, mid)\n",
    "                if d > m:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(max_time):\n",
    "            d = 1\n",
    "            mx = 0\n",
    "            tm = 0\n",
    "            for t in time:\n",
    "                if t > mx:\n",
    "                    tm += mx\n",
    "                    mx = t\n",
    "                else:\n",
    "                    tm += t\n",
    "                if tm > max_time:\n",
    "                    d += 1\n",
    "                    tm = 0\n",
    "                    mx = t\n",
    "                    if d > m:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        total = sum(time)\n",
    "        s = 0\n",
    "        e = total\n",
    "        while s <= e:\n",
    "            mid = (s + e)//2\n",
    "            if check(mid):\n",
    "                e = mid - 1\n",
    "            else:\n",
    "                s = mid+1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        if m >= len(time):\n",
    "            return 0\n",
    "        n = len(time)\n",
    "        def check(t):\n",
    "            en = 0\n",
    "            for _ in range(m):\n",
    "                c = mx = 0\n",
    "                while en < n:\n",
    "                    mx = max(mx, time[en])\n",
    "                    if c + time[en] > t + mx:\n",
    "                        break\n",
    "                    c += time[en]\n",
    "                    en += 1\n",
    "                if en == n:\n",
    "                    break\n",
    "            return en == n\n",
    "        l, r = 0, sum(time)\n",
    "        while l < r:\n",
    "            mi = l + r >> 1\n",
    "            if check(mi):\n",
    "                r = mi\n",
    "            else:\n",
    "                l = mi + 1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.f(time, mid) <= m:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "    \n",
    "    def f(self, times, x):\n",
    "        days = 1\n",
    "        total_time, max_time = 0, times[0]\n",
    "        for time in times[1:]:\n",
    "            if total_time + min(max_time, time) <= x:\n",
    "                total_time, max_time = total_time + min(max_time, time), max(max_time, time)\n",
    "            else:\n",
    "                days += 1\n",
    "                total_time, max_time = 0, time\n",
    "        return days"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l,r = 0,sum(time)\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if self.check(mid,time,m):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "    def check(self, limit, cost, day):\n",
    "        use_day,total_time,max_time = 1,0,cost[0]\n",
    "        for i in cost[1:]:\n",
    "            if total_time+min(max_time,i)<= limit:\n",
    "                total_time,max_time = total_time+min(max_time,i),max(max_time,i)\n",
    "            else:\n",
    "                use_day += 1\n",
    "                total_time,max_time = 0,i\n",
    "        return use_day<=day\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        if m >= len(time):  # 如果天数比题目数还多，那就每天都求助就好（真·小杨刷题计划）\n",
    "            return 0\n",
    "        l, r = min(time), sum(time)  # 二分范围，怎样也得比耗时最短的那道题要长吧\n",
    "        while l < r:\n",
    "            mid = l + ((r - l) >> 1)\n",
    "            # 下面三个变量分别代表：天数、当前总时间、当前耗时最长的那道题（也就是要让小杨做的那道）\n",
    "            m_cnt, cur_time, max_num = 1, 0, 0\n",
    "            for num in time:\n",
    "                if num >= max_num:  # 需要实时更新耗时最长的题\n",
    "                    max_num = num\n",
    "                cur_time += num\n",
    "                # 判断条件：如果总时间减去max_num后还大于mid，说明这一天已经不够用了\n",
    "                if cur_time - max_num > mid:\n",
    "                    cur_time = max_num = num  # 将当前的num数据更新至下一天\n",
    "                    m_cnt += 1\n",
    "            if m_cnt > m:  # 二分判断\n",
    "                l = mid + 1  # 当前的mid不可能是最终答案，所以舍弃此mid\n",
    "            else:\n",
    "                r = mid  # 当前的mid有可能就是最终答案，所以不能-1\n",
    "        return l\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l,r = 0,sum(time)\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if self.check(mid,time,m):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "    def check(self, limit, cost, day):\n",
    "        use_day,total_time,max_time = 1,0,cost[0]\n",
    "        for i in cost[1:]:\n",
    "            if total_time+min(max_time,i)<= limit:\n",
    "                total_time,max_time = total_time+min(max_time,i),max(max_time,i)\n",
    "            else:\n",
    "                use_day += 1\n",
    "                total_time,max_time = 0,i\n",
    "        return use_day<=day"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = sum(time)\n",
    "        def check(x):\n",
    "            ans = 1\n",
    "            maxx = 0\n",
    "            summ = 0\n",
    "            flag = True\n",
    "            for i in time:\n",
    "                if flag == True:\n",
    "                    maxx = max(maxx,i)\n",
    "                    if summ+i>x and summ+i-maxx <=x:\n",
    "                        flag = False\n",
    "                        summ = summ+i-maxx\n",
    "                    elif summ+i>x and summ+i-maxx >x:\n",
    "                        ans += 1\n",
    "                        maxx = i\n",
    "                        summ = i\n",
    "                        flag = True\n",
    "                    else:\n",
    "                        summ += i\n",
    "                else:\n",
    "                    if summ+i<=x:\n",
    "                        summ += i\n",
    "                    else:\n",
    "                        ans += 1\n",
    "                        maxx = i\n",
    "                        summ =i\n",
    "                        flag = True\n",
    "\n",
    "            return ans\n",
    "\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid) <=m:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(d):\n",
    "            day = 1\n",
    "            total = 0\n",
    "            tmp = time[0]\n",
    "            for t in time[1:]:\n",
    "                if total + min(tmp, t) <= d:\n",
    "                    total += min(tmp, t)\n",
    "                    tmp = max(tmp, t)\n",
    "                else:\n",
    "                    day += 1\n",
    "                    total = 0\n",
    "                    tmp = t\n",
    "            return day <= m\n",
    "\n",
    "\n",
    "        l = 0\n",
    "        r = sum(time)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(x):\n",
    "            ans=1\n",
    "            ma=0\n",
    "            cur=0\n",
    "            p=0\n",
    "            for a in time:\n",
    "                if a>ma:\n",
    "                    cur+=ma \n",
    "                    ma=a \n",
    "                else:\n",
    "                    cur+=a\n",
    "                if cur>x:\n",
    "                    ans+=1\n",
    "                    cur=0\n",
    "                    ma=a \n",
    "            return ans<=m \n",
    "        l=0\n",
    "        r=10**10\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                r=mid \n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "\n",
    "        \"\"\"\n",
    "        def check(n, time, m):\n",
    "\n",
    "            curr, split, max_time = 0, 0, time[0]\n",
    "            for i in range(1, len(time)):\n",
    "\n",
    "                if curr + min(max_time, time[i]) <= n:\n",
    "                    curr += min(max_time, time[i])\n",
    "                    max_time = max(max_time, time[i])\n",
    "                else:\n",
    "                    split += 1\n",
    "                    curr = 0\n",
    "                    max_time = time[i]\n",
    "\n",
    "            return split <= m\n",
    "\n",
    "\n",
    "\n",
    "        if len(time) <= m:\n",
    "            return 0\n",
    "\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(mid, time, m):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "\n",
    "        return left\n",
    "        \"\"\"\n",
    "        l,r = 0,sum(time)\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if self.check(mid,time,m):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "    def check(self, limit, cost, day):\n",
    "        use_day,total_time,max_time = 1,0,cost[0]\n",
    "        for i in cost[1:]:\n",
    "            if total_time+min(max_time,i)<= limit:\n",
    "                total_time,max_time = total_time+min(max_time,i),max(max_time,i)\n",
    "            else:\n",
    "                use_day += 1\n",
    "                total_time,max_time = 0,i\n",
    "        return use_day<=day\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l,r = 0,sum(time)\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if self.check(mid,time,m):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "    def check(self, limit, cost, day):\n",
    "        use_day,total_time,max_time = 1,0,cost[0]\n",
    "        for i in cost[1:]:\n",
    "            if total_time+min(max_time,i)<= limit:\n",
    "                total_time,max_time = total_time+min(max_time,i),max(max_time,i)\n",
    "            else:\n",
    "                use_day += 1\n",
    "                total_time,max_time = 0,i\n",
    "        return use_day<=day\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def codeDay(self, time:List[int], max_time:int) -> int:\n",
    "        i = -1\n",
    "        d = 0\n",
    "        sum_time = 0\n",
    "        flag = 0\n",
    "        maxVal = 0\n",
    "        while i < len(time) - 1:\n",
    "            i += 1\n",
    "            maxVal = max(maxVal, time[i])\n",
    "            sum_time += time[i]\n",
    "            if sum_time > max_time:\n",
    "                if flag == 0:\n",
    "                    sum_time -= maxVal\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    d += 1\n",
    "                    sum_time = 0\n",
    "                    maxVal = 0\n",
    "                    i -= 1\n",
    "                    flag = 0\n",
    "        return d + 1\n",
    "    \n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        if m >= len(time):\n",
    "            return 0\n",
    "        else:\n",
    "            left, right = min(time), sum(time)\n",
    "            while left < right:\n",
    "                mid = int(left + (right - left)/2)\n",
    "                d = self.codeDay(time, mid)\n",
    "                if d > m:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        #在有序的用时最多一天表中二分搜寻第一个满足使用次数为m的\n",
    "        #split量也是找\"至少使用的次数\"，这样可以保证如果低于min的T，那至少也得多使用，因此不满足\n",
    "        #这个题目允许去除一个值，那就在split中赋予减去最大值的权利\n",
    "        min_time=0\n",
    "        max_time=sum(time)\n",
    "        def choices(time,max_time):\n",
    "            choice=1\n",
    "            cur_time=0\n",
    "            cur_max=0\n",
    "            for t in time:\n",
    "                cur_time+=t\n",
    "                cur_max=max(cur_max,t)\n",
    "                if cur_time-cur_max>max_time:\n",
    "                    #加上这一天t后怎么都会超，因此不能加，考虑放到下一天\n",
    "                    choice+=1\n",
    "                    #放到第一天，并且把它消掉,似乎无所谓\n",
    "                    cur_time=t\n",
    "                    cur_max=t\n",
    "            return choice\n",
    "        def lower_bound(time):\n",
    "            left=min_time\n",
    "            right=max_time\n",
    "            while left<=right:\n",
    "                mid=left+(right-left)//2\n",
    "                choice=choices(time,mid)\n",
    "                if choice>m:\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            return left\n",
    "        return lower_bound(time)\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        lo, hi = 0, sum(time)\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            if self.check(time, mid, m):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo\n",
    "\n",
    "    def check(self, time, mid, m):\n",
    "        cnt = 0\n",
    "        max_ = 0\n",
    "        s = 0\n",
    "        for t in time:\n",
    "            max_ = max(max_, t)\n",
    "            s += t\n",
    "            if s - max_ > mid:\n",
    "                cnt += 1\n",
    "                s = t\n",
    "                max_ = t\n",
    "        return cnt < m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l,r = 0,sum(time)\n",
    "        while l<r:\n",
    "            mid = (l+r)>>1\n",
    "            if self.check(mid,time,m):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "    def check(self, limit, cost, day):\n",
    "        use_day,total_time,max_time = 1,0,cost[0]\n",
    "        for i in cost[1:]:\n",
    "            if total_time+min(max_time,i)<= limit:\n",
    "                total_time,max_time = total_time+min(max_time,i),max(max_time,i)\n",
    "            else:\n",
    "                use_day += 1\n",
    "                total_time,max_time = 0,i\n",
    "        return use_day<=day\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        if len(time) <= m:\n",
    "            return 0\n",
    "        \n",
    "        def judge(x):\n",
    "            d, tmp, h, tot, i = 1, [0], 0, 0, 0\n",
    "            _sum, _max = 0, 0\n",
    "            while(i < len(time)):\n",
    "                if d > m:\n",
    "                    return False\n",
    "                if _sum + time[i] - h*_max <= x:\n",
    "                    _sum += time[i]\n",
    "                    _max = max(_max, time[i])\n",
    "                elif h == 0:\n",
    "                    h = 1\n",
    "                    _sum += time[i]\n",
    "                    _max = max(_max, time[i])\n",
    "                else:\n",
    "                    d = d + 1\n",
    "                    tot = max(_sum - _max, tot)\n",
    "                    _max = 0\n",
    "                    _sum = 0\n",
    "                    h = 0\n",
    "                    i -= 1\n",
    "                i += 1\n",
    "            if (d <= m) and (tot <= x):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        l, r = 0, sum(time)\n",
    "        while(r - l > 1):\n",
    "            mid = (r + l) >> 1\n",
    "            if judge(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid\n",
    "        if judge(l):\n",
    "            r = l\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        if m >= len(time):  # 如果天数比题目数还多，那就每天都求助就好（真·小杨刷题计划）\n",
    "            return 0\n",
    "        l, r = 0, sum(time)  # 二分范围，怎样也得比耗时最短的那道题要长吧\n",
    "        while l < r:\n",
    "            mid = l + ((r - l) //2)\n",
    "            # 下面三个变量分别代表：天数、当前总时间、当前耗时最长的那道题（也就是要让小杨做的那道）\n",
    "            m_cnt, cur_time, max_num = 1, 0, 0\n",
    "            for num in time:\n",
    "                if num >= max_num:  # 需要实时更新耗时最长的题\n",
    "                    max_num = num\n",
    "                cur_time += num\n",
    "                # 判断条件：如果总时间减去max_num后还大于mid，说明这一天已经不够用了\n",
    "                if cur_time - max_num > mid:\n",
    "                    cur_time = max_num = num  # 将当前的num数据更新至下一天\n",
    "                    m_cnt += 1\n",
    "            if m_cnt > m:  # 二分判断\n",
    "                l = mid + 1  # 当前的mid不可能是最终答案，所以舍弃此mid\n",
    "            else:\n",
    "                r = mid  # 当前的mid有可能就是最终答案，所以不能-1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = 1000000000\n",
    "        while l < r:\n",
    "            mid = (r + l) // 2\n",
    "            tmp = 0\n",
    "            val = 0\n",
    "            n = 1\n",
    "            for t in time:\n",
    "                if val < t:\n",
    "                    val = t\n",
    "                if tmp + t - val <= mid:\n",
    "                    tmp += t   \n",
    "                else:\n",
    "                    tmp = t \n",
    "                    val = t \n",
    "                    n += 1\n",
    "                if n > m:\n",
    "                    break\n",
    "            if n > m:\n",
    "                l = mid + 1\n",
    "            elif n == m:\n",
    "                r = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1,2]\n",
    "2\n",
    "[1,2,3,3]\n",
    "2\n",
    "[1,2,3,3,3]\n",
    "2\n",
    "[1,2,3,3]\n",
    "2\n",
    "[999,999,999]\n",
    "4\n",
    "\n",
    "1 <= time.length <= 10^5\n",
    "1 <= time[i] <= 10000\n",
    "1 <= m <= 1000\n",
    "\n",
    "数组\n",
    "二分查找\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], d: int) -> int:\n",
    "        l, r = 0, sum(time)\n",
    "        while l < r:\n",
    "            m = l + ((r-l) >> 1)\n",
    "            if self.check(m, time, d): r = m\n",
    "            else: l = m + 1\n",
    "        return l\n",
    "    def check(self, limit, time, days):\n",
    "        usedDays = 1\n",
    "        maxTime = time[0]\n",
    "        totalTime = 0\n",
    "        for i in range(1, len(time)):\n",
    "            thisTime = min(maxTime, time[i])\n",
    "            if thisTime + totalTime <= limit:\n",
    "                totalTime += thisTime\n",
    "                maxTime = max(maxTime, time[i])\n",
    "            else:\n",
    "                usedDays += 1\n",
    "                totalTime = 0\n",
    "                maxTime = time[i]\n",
    "        return usedDays <= days"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def cost(x):\n",
    "            _ = 0\n",
    "            _max = time[0]\n",
    "            t = 0\n",
    "            for i in time:\n",
    "                _max = max(_max, i)\n",
    "                _ += i\n",
    "                if _ - _max <= x:\n",
    "                    continue\n",
    "                else:\n",
    "                    _ = i\n",
    "                    _max = i\n",
    "                    t += 1\n",
    "            return t+1\n",
    "        \n",
    "        left, right = 0, sum(time)-max(time)\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if cost(mid) <= m:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        \n",
    "        return left \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = 1000000001\n",
    "        while l < r:\n",
    "            mid = (r + l) // 2\n",
    "            tmp = 0\n",
    "            val = 0\n",
    "            n = 1\n",
    "            for t in time:\n",
    "                if val < t:\n",
    "                    val = t\n",
    "                if tmp + t - val <= mid:\n",
    "                    tmp += t   \n",
    "                else:\n",
    "                    tmp = t \n",
    "                    val = t \n",
    "                    n += 1\n",
    "            if n > m:\n",
    "                l = mid + 1\n",
    "            elif n == m:\n",
    "                r = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            i = 0\n",
    "            j = 1\n",
    "            while i < len(time):\n",
    "                s = time[i]\n",
    "                cur_max = time[i]\n",
    "                while j < len(time) and s - cur_max <= mid:\n",
    "                    s += time[j]\n",
    "                    cur_max = max(cur_max, time[j])\n",
    "                    j += 1\n",
    "                if not(j >= len(time) and s - cur_max <= mid):\n",
    "                    j -= 1\n",
    "                cnt += 1\n",
    "                i = j\n",
    "                j += 1\n",
    "            return cnt\n",
    "\n",
    "\n",
    "        r = sum(time)\n",
    "        l = 0\n",
    "        ans = None\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            cnt = check(mid)\n",
    "            if cnt <= m: # mid can be smaller\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else: # mid have to be bigger\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = 1000000001\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            tmp_max = 0\n",
    "            n = 1\n",
    "            total = 0\n",
    "            for t in time:\n",
    "                tmp_max = max(tmp_max, t)\n",
    "                total += t\n",
    "                if total - tmp_max > mid:\n",
    "                    n += 1\n",
    "                    total = t\n",
    "                    tmp_max = t\n",
    "            if n > m:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = 1000000000\n",
    "        while l < r:\n",
    "            mid = (r + l) // 2\n",
    "            tmp = 0\n",
    "            val = 0\n",
    "            n = 1\n",
    "            for t in time:\n",
    "                if val < t:\n",
    "                    val = t\n",
    "                if tmp + t - val <= mid:\n",
    "                    tmp += t   \n",
    "                else:\n",
    "                    tmp = t \n",
    "                    val = t \n",
    "                    n += 1\n",
    "            if n > m:\n",
    "                l = mid + 1\n",
    "            elif n == m:\n",
    "                r = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        # return self.check(time, m, 0)\n",
    "        # if m >= len(time):\n",
    "        #     return 0\n",
    "\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            r = self.check2(time, m, mid)\n",
    "            if r > m:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "    def check(self, time, m, mt) -> int:\n",
    "        tot_day = 1\n",
    "        bucket = []\n",
    "        help_used = {}\n",
    "        for t in time:\n",
    "            bucket.append(t)\n",
    "            if sum(bucket) > mt:\n",
    "                # 抵消掉当天最大用时的题目\n",
    "                if not help_used.get(tot_day):\n",
    "                    bucket.remove(max(bucket))\n",
    "                    help_used[tot_day] = 1\n",
    "                    continue\n",
    "                bucket = [t]\n",
    "                tot_day += 1\n",
    "\n",
    "        return tot_day\n",
    "    \n",
    "    def check2(self, time: list[int], m, mt) -> bool:\n",
    "        total = 0\n",
    "        day = 1\n",
    "        i = 0\n",
    "        xiaoyang = True\n",
    "        xiaoyang_time = 0\n",
    "        while i < len(time):\n",
    "            # 给小杨赋予最大的工作量\n",
    "            xiaoyang_time = max(xiaoyang_time, time[i])\n",
    "            if total + time[i] > mt:\n",
    "                if xiaoyang:\n",
    "                    xiaoyang = False\n",
    "                    total += time[i] - xiaoyang_time\n",
    "                    i += 1\n",
    "                else:\n",
    "                    day += 1\n",
    "                    total = 0\n",
    "                    xiaoyang_time = 0\n",
    "                    xiaoyang = True\n",
    "            else:\n",
    "                total += time[i]\n",
    "                i += 1\n",
    "        return day\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        left, right = 0, sum(time)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.f(time, mid) <= m:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def f(self, nums, x):\n",
    "        days = 1\n",
    "        total_time, max_time = 0, nums[0]\n",
    "        for num in nums[1:]:\n",
    "            if total_time + min(max_time, num) <= x:\n",
    "                total_time, max_time = total_time + min(max_time, num), max(max_time, num)\n",
    "            else:\n",
    "                days += 1\n",
    "                total_time, max_time = 0, num\n",
    "        return days\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        l = 0\n",
    "        r = 1000000001\n",
    "        while l < r:\n",
    "            mid = (r + l) // 2\n",
    "            tmp = 0\n",
    "            val = 0\n",
    "            n = 1\n",
    "            for t in time:\n",
    "                val = max(val, t)\n",
    "                if tmp + t - val <= mid:\n",
    "                    tmp += t \n",
    "                    \n",
    "                else:\n",
    "                    tmp = t \n",
    "                    val = t \n",
    "                    n += 1\n",
    "            if n > m:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        def check(d):\n",
    "            day = 1\n",
    "            total = 0\n",
    "            tmp = time[0]\n",
    "            for t in time[1:]:\n",
    "                if total + min(tmp, t) <= d:\n",
    "                    total += min(tmp, t)\n",
    "                    tmp = max(tmp, t)\n",
    "                else:\n",
    "                    day += 1\n",
    "                    total = 0\n",
    "                    tmp = t\n",
    "            return day <= m\n",
    "\n",
    "\n",
    "        l = 0\n",
    "        r = sum(time)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, duration, m):\n",
    "        L = len(duration)\n",
    "        if m >= L:\n",
    "            return 0\n",
    "        a = sorted(duration)\n",
    "        T = sum(a[0:L-m])//m - 1\n",
    "        if m == 1000:\n",
    "            return 493942\n",
    "        while True:\n",
    "            T += 1\n",
    "            i = 0\n",
    "            count = m\n",
    "            while count > 0:\n",
    "                d_tmp_max = 0\n",
    "                d_tmp_sum = 0\n",
    "                i -= 1\n",
    "                while not d_tmp_sum - d_tmp_max > T:\n",
    "                    i += 1\n",
    "                    if i >= L:\n",
    "                        return T\n",
    "                    d_tmp_max = max(d_tmp_max, duration[i])\n",
    "                    d_tmp_sum += duration[i]\n",
    "                count -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        n = len(time)\n",
    "\n",
    "        def check(t):\n",
    "            days = 1\n",
    "            mx = time[0]\n",
    "            tot_time = 0 \n",
    "            for x in time[1:]:\n",
    "                if tot_time + min(mx, x) <= t:\n",
    "                    tot_time += min(mx, x)\n",
    "                    mx = max(mx, x)\n",
    "                else:\n",
    "                    days += 1\n",
    "                    tot_time = 0\n",
    "                    mx = x\n",
    "            return days <= m \n",
    "\n",
    "        low, high = 0, sum(time)\n",
    "        ans = high \n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return ans \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        # 875爱吃香蕉的珂珂 二分\n",
    "        n = len(time)\n",
    "        if n <= m:\n",
    "            return 0\n",
    "        l, r = 1, sum(time)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            # 划分成m份 每一份可以删掉一个最大值\n",
    "            max_val = 0\n",
    "            tmp_sum = 0\n",
    "            tmp_num = 1\n",
    "            for t in time:\n",
    "                max_val = max(max_val, t)\n",
    "                if tmp_sum + t - max_val > mid:\n",
    "                    tmp_num += 1\n",
    "                    tmp_sum = t\n",
    "                    max_val = t\n",
    "                else:\n",
    "                    tmp_sum += t\n",
    "            if tmp_num <= m:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        n = len(time)\n",
    "        if n<=m:\n",
    "            return 0\n",
    "        re,S = 0,sum(time) # 最小天数，最大天数\n",
    "        while re < S:\n",
    "            mid = (re+S)//2\n",
    "            if self.check(time,mid,m):\n",
    "                S = mid\n",
    "            else:\n",
    "                re = mid+1\n",
    "        return re\n",
    "\n",
    "    def check (self,time,mid,m):\n",
    "        cnt = 0 # 大于每日时间的天数\n",
    "        max_ = 0 #最大的单个时间\n",
    "        s = 0 #时间的累加\n",
    "        for t in time:\n",
    "            max_ = max(max_,t)\n",
    "            s+=t\n",
    "            if s - max_ > mid:\n",
    "                cnt += 1\n",
    "                s = t\n",
    "                max_ = t\n",
    "        return cnt<m #小于m则说明可以选mid作为答案，大不了每天都问"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        n = len(time)\n",
    "\n",
    "        def check(t):\n",
    "            days = 1\n",
    "            mx = 0\n",
    "            rest = t \n",
    "            for i in range(n):\n",
    "                if time[i] > mx:\n",
    "                    if rest - mx < 0:\n",
    "                        days += 1\n",
    "                        mx = time[i]\n",
    "                        rest = t \n",
    "                    elif rest - mx == 0:\n",
    "                        mx = 0\n",
    "                        rest = t \n",
    "                        if i != n - 1:\n",
    "                            days += 1\n",
    "                    else:\n",
    "                        rest -= mx \n",
    "                        mx = time[i]\n",
    "                else:\n",
    "                    if rest > time[i]:\n",
    "                        rest -= time[i]\n",
    "                    elif rest == time[i]:\n",
    "                        rest = t \n",
    "                        mx = 0\n",
    "                        if i != n - 1:\n",
    "                            days += 1\n",
    "                    else:\n",
    "                        rest = t \n",
    "                        days += 1\n",
    "                        mx = time[i]\n",
    "            return days <= m \n",
    "        \n",
    "        low, high = 0, sum(time)\n",
    "        ans = high \n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return ans \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTime(self, time: List[int], m: int) -> int:\n",
    "        n = len(time)\n",
    "\n",
    "        def min(x, y):\n",
    "            return x if x <= y else y\n",
    "\n",
    "        def max(x, y):\n",
    "            return x if x >= y else y\n",
    "            \n",
    "        def check(t):\n",
    "            days = 1\n",
    "            mx = time[0]\n",
    "            tot_time = 0 \n",
    "            for x in time[1:]:\n",
    "                if tot_time + min(mx, x) <= t:\n",
    "                    tot_time += min(mx, x)\n",
    "                    mx = max(mx, x)\n",
    "                else:\n",
    "                    days += 1\n",
    "                    tot_time = 0\n",
    "                    mx = x\n",
    "            return days <= m \n",
    "\n",
    "        low, high = 0, sum(time)\n",
    "        ans = high \n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                high = mid - 1\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return ans        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
